package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC291 {

    static class Solution {
        /**
         * @param edge: edge[i][0] [1] [2]  start point,end point,value
         * @return: return the second diameter length of the tree
         */
        public long getSecondDiameter(int[][] edge) {
            //树的直径理论： https://www.cnblogs.com/cjl-world/p/13704893.html
            //从树上任意一个点出发所到达的最远的点一定是树的两个端点之一。
            int n = edge.length; //边数
            //构建图，图的顶点数要比边数多1个
            Map<Integer,Set<Node>> g =buildGraph(n+1,edge);
            Node path1 = bfs(0,g);
            Node path2 = bfs(path1.data,g);
            Node path3 = bfs(path2.data,g);

            return Math.max(path2.distance,path3.distance);
        }

        //图的bfs
        public Node bfs(int root,Map<Integer,Set<Node>> g){
            Queue<Integer> q = new LinkedList<>();
            int first=root,second = root;
            Map<Integer,Long> disToRoot = new HashMap<>();
            disToRoot.put(root,0L);
            q.add(root);

            while (!q.isEmpty()){
                int pop = q.poll();
                Set<Node> nexts = g.get(pop);
                for (Node next : nexts) {
                    if(disToRoot.containsKey(next.data)) continue;
                    long distance = disToRoot.get(pop)+ next.distance;
                    if(distance > disToRoot.get(first)){
                        second = first;
                        first = next.data;
                    }else if(distance> disToRoot.get(second)){
                        second = next.data;
                    }

                    disToRoot.put(next.data,distance);
                    q.add(next.data);
                }
            }
            return new Node(first,disToRoot.get(second));
        }

        public Map<Integer,Set<Node>> buildGraph(int points,int[][] edge){
            Map<Integer,Set<Node>> g = new HashMap<>();
            for (int i = 0; i <points ; i++) {
                g.put(i,new HashSet<>());
            }
            for (int[] v : edge) {
                g.get(v[0]).add(new Node(v[1],v[2]));
                g.get(v[1]).add(new Node(v[0],v[2]));
            }
            return g;
        }
        static class Node{
            public int data;
            public long distance;
            public Node(int d,long di){
                data =d;
                distance=di;
            }
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.getSecondDiameter(new int[][]{{0,1,4},{0,2,7}}));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有216条未读消息，请及时查看
291 · 第二直径
算法
中等
通过率
41%

题目
题解8
笔记
讨论20
排名
记录
描述
给出由
n
n个结点，
n
−
1
n−1条边组成的一棵树。求这棵树的第二直径，也就是两两点对之间距离的次大值。
给出大小为
(
n
−
1
)
×
3
(n−1)×3的数组edge,edge[i][0],edge[i][1],edge[i][2],表示第i条边是从edge[i][0]连向edge[i][1]，长度为edge[i][2]的无向边。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


2
≤
n
≤
1
0
5
2≤n≤10
5


1
≤
e
d
g
e
[
i
]
[
2
]
≤
1
0
5
1≤edge[i][2]≤10
5


因为DFS(Depth-First-Search)容易爆栈，请使用BFS(Breadth First Search)完成该题目
如果有多个点对的距离都是最长，那么你只需要返回最长距离即可~

样例
输入:[[0,1,4],[0,2,7]]
输出:7
解释:两两之间的次大值为0到2的7

标签
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
